
/******************/
/* TP5 - GRUPO 13 */
/******************/
/* Andre Bonna    */
/* Artur Gontijo  */
/* Ivo Trivella   */
/******************/


#include "arvbp.h"



/* ------------------------------------------------------------------- */

/* Insere uma Chave na Arvore */
void Insere(int inteiro){

  int cont=0, x=0, Narq=0, vetor[ORDEM], i=0, teste=0;
  Noh Node;

  if(Narq == 0){
    /* Caso Generico */
    
    Node.tam = 0;
    for(cont=0; cont < ORDEM; cont++){
      Node.keys[cont] = -1;
    }
    for(cont=0; cont < ORDEM+1; cont++){
      Node.proxk[cont] = -1;
    }
    
    Node.direita = -1;            
    Node.esquerda = -1;            
    Node.Narq = Narq;                
    Node.folha = 1;                
    
    /* Fim (Caso Generico) */
  }

  while(1){

    teste = 0;
    Node.tam = 0;
    LeNoh(&Node, Narq);

    if(Node.tam < ORDEM){
      
      Node.tam++;
      for(cont=0;cont < Node.tam; cont++){
	if(Node.keys[cont] > inteiro){
	  for(x=cont; x < ORDEM; x++){
	    vetor[i] = Node.keys[x];
	    i++;
	  }
	  Node.keys[cont] = inteiro;
	  i=0;
	  for(x=cont+1; x < ORDEM; x++){
	    Node.keys[x] = vetor[i];
	    i++;
	  }
	  teste = 1;
	  break;
	} 
      }
      if(cont == Node.tam){ 
	Node.keys[Node.tam-1] = inteiro;
	teste = 1;
      }
      if(Node.tam == ORDEM){
	Node.folha = 0;
      }
      GravaNoh(&Node);
    } else teste = 0;
  
    if(teste != 1) {

      Narq++;
      /* Caso Generico */
      
      Node.tam = 0;
      for(cont=0; cont < ORDEM; cont++){
	Node.keys[cont] = -1;
      }
      for(cont=0; cont < ORDEM+1; cont++){
	Node.proxk[cont] = -1;
      }
      
      Node.direita = -1;            
      Node.esquerda = -1;            
      Node.Narq = Narq;                
      Node.folha = 1;                
      
      /* Fim (Caso Generico) */

    }
    else break;    
  }

  
  return;
}

/* ------------------------------------------------------------------- */

/* Verifica se um Determinado Noh jah existe ou Nao na Arvore */
int Verifica(int num, int chave){
  int res;

  res = Busca(chave);
  
  if(res != -1) return 1;
  else return 0;
}

/* ------------------------------------------------------------------- */

/* Remove uma Chave da Arvore */
void Remove(int raiz, int chave){
  int res, i, x, vetor[ORDEM];
  Noh node;

  res = Busca(chave);
  
  if(res != -1) {
    printf("\n\nNumero nao encontrado!!\n\n");
    return;
  }
  else {
    LeNoh(&node, res);
    for(i=0; i<node.tam; i++){
      vetor[i] = node.keys[i];
      if(node.keys[i] == chave){
	for(x=i; x<node.tam; x++){
	  vetor[x] = node.keys[x+1];
	}
	for(x=0; x<node.tam; x++){
	  node.keys[x] = vetor[x];
	}
	node.tam--;
      }
    }
    GravaNoh(&node);
  }
}

/* ------------------------------------------------------------------- */

/* Busca por uma Chave na Arvore: retorna o numero do arquivo */
int Busca(int chave){
  int i, num=0;
  char nomearq[NOMEARQTAM];
  FILE *teste;
  Noh no1;

  while(1){
    LeNoh(&no1, num);
    
    for(i=0; i<no1.tam; i++){
      if(no1.keys[i] == chave){
	return num;
      }
    }

    sprintf(nomearq, "%d.arv", num+1);
    teste = fopen(nomearq,"r");
    if(teste == NULL) return -1;
    else fclose(teste);

    num++;
  }
}

/* ------------------------------------------------------------------- */

/* Lista todas as Chaves da Arvore */
void Lista(FILE **arq){
  
  int cont=0;
  char nomearq[NOMEARQTAM];

  Noh *Node;
  
  sprintf(nomearq, "%d.arv", cont);
  *arq = fopen(nomearq, "r");

  while(*arq != NULL) {

    printf("NODE = %d\n", cont);
    fscanf(*arq, "%d", &Node->folha);
    fscanf(*arq, "%d", &Node->tam);

    for(cont=0; cont < Node->tam; cont++){
      fscanf(*arq, "%d ", &Node->keys[cont]);
      printf("%d ", Node->keys[cont]);
    }

    printf("\n");

    for(cont=0; cont < (Node->tam+1); cont++){
      fscanf(*arq, "%d ", &Node->proxk[cont]);
      printf("%d ", Node->proxk[cont]);
    }

    printf("\n");

    fscanf(*arq, "%d", &Node->esquerda);
    fscanf(*arq, "%d", &Node->direita);

    fclose(*arq);

    cont++;
    sprintf(nomearq, "%d.arv", cont);
    *arq = fopen(nomearq, "r");

  }

  free(Node);
  
  return;
}

/* ------------------------------------------------------------------- */

/* Le o Conteudo de um Noh do Arquivo */
void LeNoh(Noh *Node, int Narq){
  
  int cont=0;
  char nomearq[NOMEARQTAM];

  FILE *arq;
  
  Node->Narq = Narq;
  
  sprintf(nomearq, "%d.arv", Narq);
  arq = fopen(nomearq, "r");

  if(arq != NULL) {

    fscanf(arq, "%d", &Node->folha);
    fscanf(arq, "%d", &Node->tam);

    for(cont=0; cont < Node->tam; cont++){
      fscanf(arq, "%d", &Node->keys[cont]);
    }

    for(cont=0; cont < (Node->tam+1); cont++){
      fscanf(arq, "%d", &Node->proxk[cont]);
    }

    fscanf(arq, "%d", &Node->esquerda);
    fscanf(arq, "%d", &Node->direita);

  }
  
}

/* ------------------------------------------------------------------- */

/* Grava um Noh da RAM para o Arquivo */
void GravaNoh(Noh *Node){
  
  int cont=0;
  char nomearq[NOMEARQTAM];

  FILE *arq;
  
  sprintf(nomearq, "%d.arv", Node->Narq);
  arq = fopen(nomearq, "w");
  
  fprintf(arq, "%d\n", Node->folha);
  fprintf(arq, "%d\n", Node->tam);
  
  for(cont=0; cont < Node->tam; cont++){
    fprintf(arq, "%d ", Node->keys[cont]);
  }

  fprintf(arq, "\n");
  
  for(cont=0; cont < (Node->tam+1); cont++){
    fprintf(arq, "%d ", Node->proxk[cont]);
  }

  fprintf(arq, "\n");  

  fprintf(arq, "%d\n", Node->esquerda);
  fprintf(arq, "%d\n", Node->direita);

  fclose(arq);
}

/* ------------------------------------------------------------------- */

/* Dah um Split na Arvore, caso Necessario */
void Split(int teste, int teste2){
  
  printf("SPLIT....\n");
  getchar();
  return;
}

/* ------------------------------------------------------------------- */
